An index, also known as data dictionary or associative array, is a data structure and associated algorithms that are used to map identifying values, known as keys, to associated values, also known as satellite data. The concatenation of the key and its satellite data comprise one embodiment of a record data entry.
In one example, an index is broken into buckets, each bucket having enough room for up to N record data entries, for example, 30. The bucket has a size field e.g., 512 bytes, indicating how many records can fit in the bucket. Record data entries may be stored in the bucket in sorted order, in time order (the order in which they arrive), or an indirection table may be used for storing the record data entries in an arbitrary order. Various algorithms have been used for allocating record data entries to buckets, typically with a goal of uniformly distributing the record data entries across all buckets. In some examples, multiple levels of buckets are provided to handle overflow if an initial bucket is filled.
Many applications require an index with a very large number of entries, thus requiring gigabtyes of memory to store the associated data structures, and a very high operation rate, e.g., hundreds of thousands of operations per second. Some memory technologies, such as DRAM, may provide the necessary performance, but are not dense enough to economically store such a large number of records. Other memory technologies, such as disk technology, may have the density, but not the required performance. Thus, there is an ongoing need for a memory technology that can meet both the storage size and operation rate requirements for generating and maintaining a large number of records.